###############################################################################
# Copyright 2019 StarkWare Industries Ltd.                                    #
#                                                                             #
# Licensed under the Apache License, Version 2.0 (the "License").             #
# You may not use this file except in compliance with the License.            #
# You may obtain a copy of the License at                                     #
#                                                                             #
# https://www.starkware.co/open-source-license/                               #
#                                                                             #
# Unless required by applicable law or agreed to in writing,                  #
# software distributed under the License is distributed on an "AS IS" BASIS,  #
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.    #
# See the License for the specific language governing permissions             #
# and limitations under the License.                                          #
###############################################################################

import hashlib
import itertools
import json
import math
import os
import secrets
from typing import Optional, Tuple, Union

from ...ecdsa.rfc6979 import generate_k

from .math_utils import (
    ECPoint,
    div_mod,
    div_ceil,
    ec_add,
    ec_double,
    ec_mult,
)

# TODO: require more module from sympy
# from ...sympy.ntheory.residue_ntheory import (
#     is_quad_residue,
#     sqrt_mod,
# )

FIELD_PRIME = 3618502788666131213697322783095070105623107215331596699973092056135872020481
FIELD_GEN = 3
ALPHA = 1
BETA = 3141592653589793238462643383279502884197169399375105820974944592307816406665
EC_ORDER = 3618502788666131213697322783095070105526743751716087489154079457884512865583
CONSTANT_POINTS = [
        [
            2089986280348253421170679821480865132823066470938446095505822317253594081284,
            1713931329540660377023406109199410414810705867260802078187082345529207694986
        ],
        [
            874739451078007766457464989774322083649278607533249481151382481072868806602,
            152666792071518830868575557812948353041420400780739481342941381225525861407
        ],
        [
            996781205833008774514500082376783249102396023663454813447423147977397232763,
            1668503676786377725805489344771023921079126552019160156920634619255970485781
        ],
        [
            100775230685312048816501234355008830851785728808228209380195522984287974518,
            3198314560325546891798262260233968848553481119985289977998522774043088964633
        ],
        [
            1837189741429329983886833789246131275985545035599091291966623919967841244204,
            469920083884440505232139273974987899994000885911056071194573294589259802432
        ],
        [
            1337726844298689299569036965005062374791732295462158862097564380968412485659,
            3094702644796621069343809899235459280874613277076424986270525032931210979878
        ],
        [
            2997390320399291502365701712271136720873363591256030629621859546399086933620,
            2725742381037070528763700586156979930560374472266472382691451570287013862562
        ],
        [
            3608386523905995279224196894194758246854376991737956048428718275550441491554,
            299638830690759628369563708877422667364443387620215168054000198378323554222
        ],
        [
            1733017745745290190841058775834438078769759612359153596488000160651631909868,
            1973340172374381850851160588687352250788736199336041450103281811142396650489
        ],
        [
            855657745844414012325398643860801166203065495756352613799675558543302817038,
            1379036914678019505188657918379814767819231204146554192918997656166330268474
        ],
        [
            2860710426779608457334569506319606721823380279653117262373857444958848532006,
            1390846552016301495855136360351297463700036202880431397235275981413499580322
        ],
        [
            2395624363109833935111082867579092089638282063493755655374369403894420657396,
            351237427147755677344067136337758392262982966921757802462075586166198965221
        ],
        [
            1518817631841006315871038165514435660668372956425694825094659891110110998470,
            2435234811597428668734076452595083530950234466401981561306652881621340269965
        ],
        [
            2173245854114081430013864960244839145346281378834121479101410821419573677603,
            2546798213917003006819050845641858786968858658397560158974242382076827691040
        ],
        [
            2842565516483040219247288049386440051275065340592157409909273207335045943247,
            3243970369543480657564144388570283526584293743815525434693286186817417955980
        ],
        [
            334001339911595275369567085510917903426590364565508070786916614629507192987,
            3111246400312591389547128607242178414610449977696648758380570718520342084022
        ],
        [
            1524160182224703084171959692156493185929433834577885561910744542328224256855,
            1537801596806048756579645687819844574476915843680990392821821911338917834516
        ],
        [
            1534228784878613855372285213913393282004680247144707529194564051083323737667,
            3521706376781514787959257460794337508069645724875214092054188903006114926236
        ],
        [
            2578937995141029655393232141271255572790413762563128577126763729975116228193,
            17390356333795810120168422581001175036590566546824644641783194730252048211
        ],
        [
            947940612979492942947148169286573131514814097313999984923945564630579515590,
            2308193393705297792974084886503909156992936885451139308263357445074155842124
        ],
        [
            732404465937527082089939128149870791505934917542321234949662968808570781433,
            143709480454569956048931032102611838633822436488408778496842771196869318906
        ],
        [
            241248627215637165874725355816367843299343644290443713521922700286140902436,
            3252553440660691138666231381716834106176440363202963142721270080741642531818
        ],
        [
            3333115552336678637619322993761507811794447605372046548664704236825849321847,
            2074314011440265695926966409849756773065015399410882685131987099183343980472
        ],
        [
            2828708362623152676836369441327395494506045083356924287447843608221054063061,
            107382801318187992328203770492115828936772008265759480771447426051158848300
        ],
        [
            3093728769381682918281543022553646237541394965209383769732554106568421526166,
            3204173745255459543321323207111205642245664180117592291733272407863239345733
        ],
        [
            2408410160653222627937499570601090771762354825212795227033567284727088044150,
            2304538566806563442614047090440785060491938762209719835685218901694719627776
        ],
        [
            2758360715188072223623539313334284404194065029791792170224299872004682172868,
            1002646182229402950578888347706450598176482335256655665515308125378628073404
        ],
        [
            2379910339855741683480364155463331175570260120162494489033888506779165916952,
            2649708833736663077287705299849077665696945338155198794587505679066706972556
        ],
        [
            1176714920396664309204390318351093831295503091238549055894748705033779114462,
            715774545317274898026140714630411642171682270543528864055131586173491427672
        ],
        [
            2785974441098456234843127330799770200846625265290625972155616950088804499059,
            307863489533861377687037248795744305150392367370243564208692826588510059533
        ],
        [
            3127903794657845782054923624413460963746108626701051648823597412593664219443,
            2832400994360149010034695923237223654142501296305205824531678157494587069403
        ],
        [
            1131830029003838132931634271160654858275272609594100638978880153740390535738,
            3607754722674459909791405256520586221653709952825470711876211792388292839610
        ],
        [
            2759794674261780431984200708995704387783325908768350345798229435903528807938,
            1260417916396710926345525006943606967340884567049582926597956766543273788168
        ],
        [
            2830057895043497782751868691208958763779500933641414034760294364554584648598,
            3148801330152002136119343944143478481505330324328753740340717562089558415415
        ],
        [
            2506640265270419609137616465635205683276867684162736282412466285973014171890,
            517183264945713035190384665697926865674306942691511144684578407765174829225
        ],
        [
            297135274309227547571122074141892368978567606416603548099453251059259457396,
            738308515934554491948011858951484620721581230541917718419817808748771885016
        ],
        [
            3287710003144516108009450594509223314440628263909148329742349774812346409307,
            225177091586755328705836619671963709040245082813366263262829376695813391167
        ],
        [
            1902667075164809149654789463437998238417922554649696913795190312096632954124,
            3609476325943007214468624874971854834826753291984136726633316509571578121273
        ],
        [
            3452217073856686233854377494033704667278961088549888774623466171791636016755,
            2444544408047898094236889539040891081629098003972134793849574953018755818545
        ],
        [
            2069167537346986671273731269107346759773110422380837126332493778223975152855,
            357269144817598369811221449775153952909196646906055962631273486250245080334
        ],
        [
            1047243972090526803876529530618926456830431728514494419504365869386003201726,
            493385597033162791196594107722557650629404615534399757351633988473756315396
        ],
        [
            965109286411904242713728581817485738428793211202426744037474223240067211186,
            2413690664561921424572393647761853376475215279589433231249258838213909974115
        ],
        [
            1034828486658124322341241159997750207973283714015564270100039839265723642437,
            3320659525509256706388336697822491014651786050898707765488292630053240833630
        ],
        [
            2924967592602073254569141793533465663326310402870978597207810641466195156731,
            2828397747600941786969312189630745459745605646639868710157419955197341205208
        ],
        [
            1208329771806436797417016120088886878299172415075658275611114767604464163273,
            2810710693404583496584233908768327740199404051365142000873009254465681789118
        ],
        [
            2187000042175732773516370724251479381096587891539947053664138571731476871402,
            746498189666538551392041580103908969319041062419800073057943031798594621183
        ],
        [
            2000452964676707688903182602940959322690781577603915068119089450310903786954,
            866954387631286490641992457358203082174659959202834537990114265745821626191
        ],
        [
            1296834309098498653963459206815713058813876510889656567958698555814791917906,
            900321515532234476515871433334993494171305935536543684417444011164731278279
        ],
        [
            1595376832537627540806114085753076669172519984983967639366317789074759898235,
            1219266627855965397760533984052253611682860681989985974389624113620845749733
        ],
        [
            1823240537897691300512000714094702014772232075125035605123065504505635249040,
            1906261986240090609038909222466712928329872469704972427112770233118685440655
        ],
        [
            778303663772980866291056760213466667611301230393329301216572062540133184143,
            2984789228888160339109292850517099811453943454548552440328876677370962441196
        ],
        [
            3543009119282959041814671650391719969699313481882590413207543576117841443934,
            1490213523215199378557197585333711645365263188010733339965078460230935145833
        ],
        [
            1176236937487751405961855617527764992282992896230256112304717984169523263763,
            327501310716241925530534584357204203311238806558120970999031300336125027957
        ],
        [
            2406374227501733859839714271591391036982988438954690468147627905682319529429,
            2498960794066678523664440543302013058525262611284856216226688049821146904878
        ],
        [
            3452133497919418476271423809649290075304287340106989073706651714039300732642,
            1721794031770397703814538822528137647140579794352083932468384744314312603894
        ],
        [
            1149850245936233973982137051189893468427998957468612707869248329754912343300,
            3458926667343838493950348154788263034977717528749131548957463567618227215963
        ],
        [
            889697158819326131781010711389595245311511671705340221964679483759691059211,
            2019807322878676390755723975464224869137141739292295209065143377221547630036
        ],
        [
            1115329342882491971826579323754611049286425400118842701871616630850493708107,
            279298782170669703031554266329450929495785208527313704344065678320374720785
        ],
        [
            3365519876326833923487050935023315949049714901059255282163633136201965868269,
            1868260280532817409831058300719431634773697469228981331390874154636702517757
        ],
        [
            2669519052792032403625707785046224942570603898100356640293648365762798392505,
            1740654081939116207510779753054238062700744649382792523869583125748991653229
        ],
        [
            3121331648294614359396440970780137002689430823241383158647529355695088932901,
            873685066624425351999444458200994077868639460913455806504495956245857350007
        ],
        [
            1816660828193076969492079690868149793376961857938776531133929200951688539889,
            1617163330180274180907112309026652344859788476549850480902966972316617122251
        ],
        [
            928998762106806361096934313135623561544110643422813945289044484271228303836,
            464078854784700975668790446344005332658112186605529977536203111266829995975
        ],
        [
            496484433760448456019075524089809339174015679144397089226817311073355526314,
            656343647912825200827812764729017634457244310809059156122299990679423100787
        ],
        [
            1973676598953671410920434538501081964242302598763799105681937944844095305545,
            307489436917501023536717840176704363109773690206006513056594461780393179493
        ],
        [
            518536787018692743767191710241721928752533989539898170372615978836875877432,
            2521626354257053998255710814293449754273786720271901759585107157901808273967
        ],
        [
            690595468184470683559850269431813912957862648277508592008590933748732173747,
            2414429566032394919031053748274838227119236756361308391916397575422431579532
        ],
        [
            2501095101472669025652293419986706422252484721018908950115277955062729551801,
            2787294359824056854441860940419185812333861607391901444904784313692077324784
        ],
        [
            565118044580500186326118761527011487144705745596478022906701885062524158603,
            1799231527053210762358771329838631545632111862410291843983616507220396846052
        ],
        [
            2037340835455495949556975891561839169602876578929015568690589435716642289270,
            2204387525434065888311157590483645040393870259860783204107223503007512510657
        ],
        [
            2114937389277866993631127029230629118622631637448671765297876516930885448024,
            2772043872341063054220063825377798998299638741683281348998984204361894484463
        ],
        [
            2097763236780897995115236415009286780722416534493059040644518024665003224715,
            2246556465712181592290422124919768779861225704408240007042932086214236197576
        ],
        [
            3612119898822167069923931382556535386023574823466693257258182923730749602297,
            1269484610898538742657592460359658026176515519847024771198089933933954376158
        ],
        [
            2881403268965266082547256964340568575654154178897275699709021163679539118655,
            1692819601432103623771042884269589390667189502599274435132350636867812310182
        ],
        [
            750328371578183028452365126719312491229205795053566378454173411358094968605,
            953119186030327873981560224892058145045695472203493861081607133113834466378
        ],
        [
            1656613311827787565035393466226110392419398195273172946657205368665450125099,
            2599745208280264384426758693760932474903320975443399225749144566172064401743
        ],
        [
            2103692960985198293421966097241235578982164940176248129325331384077838061492,
            2570917734334329081039835855157625956461983506342767455507599344910133039387
        ],
        [
            2956028884218562660581192985661469944972780357808337397013249554146206921192,
            408046758724714924414144046633476879802492779243354079741111917699605101737
        ],
        [
            3295092543885183250245242131201657515391353210344574951962581116320755471573,
            1642807297265426717090166824916187234878363764999511552230372565887780637331
        ],
        [
            3254747955211938731592559910914052760563649051803026767692046312174361324755,
            2597825541939769956115552787003343561035903289305000309435219987085455364052
        ],
        [
            3061661576103456171574781131851984681727274357576590194413976242212020548895,
            1440946704104779823819051619396174008908467766221900978049401983321224347705
        ],
        [
            838962129372725157269649943170983294581294061955271030939039912615696392969,
            2450855656904900531871678154573620082208900269187857841648756800522172293828
        ],
        [
            623738578803750870859101112646088321855359403665383400994605481921028955581,
            1896987617779463068695767102228909909503881877404532152457554106592081120284
        ],
        [
            3005336317328034100451063789097066979058288244531776915568829475740707033442,
            589659290793751995469380634546964377934517395448274738900772252627065284531
        ],
        [
            12756189276497641079437863756137709474617047416617345367587373008165663758,
            1456142055978131072821045695636502275738045623685201320945241755292775664199
        ],
        [
            1074674018821399880635425421583189259497571069746227839865670725436462244312,
            258858007368753107323242423300483485125794748975129950895267988132082308316
        ],
        [
            681655034855073789847960596245322342285304909895796912572444021565696961022,
            2638585878119722820634387321875125243576892120356441191562743859796708349183
        ],
        [
            484275861089119330366419813397313284916585101030604880621077715936286046362,
            2124340832207188633301820498272014794490866326891190193431359618065899307375
        ],
        [
            405073150800337564971044639647327667948449004749665061152270060911349262451,
            1489771173602690638325396124433593050299556632624187628464627170731054511183
        ],
        [
            2210274362697653963013276763896406028937726941229800687802476566182252928069,
            107281585620564596853732679859399446219714819235699352412476509704530753455
        ],
        [
            1574843453768695165378209623495036727403155857878058624836922271817659867629,
            1555661183633642518402202300513733784743599394430116656383692711334768895734
        ],
        [
            1123478630620218654285047429952065588412730975530361457071991777237712271756,
            2829567770920061439901039508116248775591132699709271161323340183772358690173
        ],
        [
            1297650053639848975729187455845252204377426797153455899043246280172874099679,
            1368877225005672215217218872501867910626338344551878492763876596080463242259
        ],
        [
            1370690034945541589206390781179695998551445194688862467131056389583582009970,
            1470539777067742221259042319802797839837448440044303811384116671245122402709
        ],
        [
            3447187626984579154758815357460309989835728867823525757738362796350869385148,
            1816603979655684111669599224323721980301208636016613170580056711560881185458
        ],
        [
            1813653163931885994109909806517422543930671118466754170167858925831571853970,
            3512341620174737184060311796746868634824078847254277831432645720920236439319
        ],
        [
            2837307695083915103816975903131537789416753154015497312646069123780420491714,
            616619065833574133353826959462642204697394233876988991826103321230494864299
        ],
        [
            594079125176886234216350989657852431152571525526195525372802362637040396383,
            2494644159641327263522333201651180948727022160625648361761185979144016156268
        ],
        [
            2908396604150117877413275805593843594741970566352971841958566678954509739722,
            2270651079544400929734484036612745055500450526594372099549710701035274374884
        ],
        [
            2678766929120334020289731872716504689707050034449508844312788171212235149009,
            335161156418784138664067328871308180390826302690183885244799298812600140579
        ],
        [
            292866251242750359983852405638782648443335655395113648998608114038199112084,
            1929874131411396072089047462553509072816290408149385625319723159940078151305
        ],
        [
            882230982554387611436849430391722624915254936568405968528170702860016504332,
            212032938028459898975134792582247420939126124794435382098720034240512634047
        ],
        [
            128726401362994700814735301317860445928097536803417431852613367962589785439,
            3394124118935926464118252583967031473364357246179309645829616988941527947171
        ],
        [
            677401161940040406778133733501716798305847724216576059351439033320244262845,
            2925999450717968641674678177839015248195288227966544952091044204990727381539
        ],
        [
            2609307202957921769201454597723184920663265694086171832237331231605229071753,
            801185762689670517839772705471851009753066843170718046248101910206876036095
        ],
        [
            3164184719276807654208802895852587431370308788690119771658913844464285523544,
            1905779810840212631464048113896329901522020622508861085333684930860131307278
        ],
        [
            3611134164349757211212839193742321198628214417127680099335976437205997336534,
            2043780132560451089266915016427409559115509465273768103961201197432849551860
        ],
        [
            674219880578998785256251799630500124321523321851449394348048261225376968813,
            3482911053866603432328977995361936638192865211341332440041477929097847986703
        ],
        [
            3592898179794583311559546383565181628347625484079136119992096748458485223135,
            1465170880570843353446345695255388397672185811127330686304727767842553737080
        ],
        [
            3479945591612641094508473900775458017345694655844890750906112888442669167437,
            3101936119331166017640859304880796239643688879875971179134677606262220157899
        ],
        [
            1109415449398025759620102870831886622665877707210305893342279346428768457000,
            2860907454930708330476655483302818728978205359193672814876717458325223426655
        ],
        [
            1357688207483205144399854674655145367528198873070486160807161516476844171794,
            2883341787687489538845947867713953817206085374003322509387259371280461173550
        ],
        [
            2673153466150226365693822405439428986034577351717746967078667507408831331822,
            1711608722888314089357865502727953201489434753448475578858737527005192231458
        ],
        [
            3399600989769963316575978481506459307955666332477901574428783938231920315833,
            3215591135790328619011904119580811201910745729655431204459208397816583809934
        ],
        [
            1836471948074401070182493369353230908796463402812051721703561360825727986274,
            2080945706738209357213401773997996954868066166149050730738271792162977075010
        ],
        [
            3078673344420931157936045314816499193943345153816528362806332351627801597029,
            1525425884468796152026606689861526369646610285280224319617687192867257228599
        ],
        [
            2722661126018430265331502523339121563282558062510457654064467493725828237046,
            2961950709147303512642570304801930511214999580227551995337732709133755475031
        ],
        [
            3274644392893639165667150492068461730297126947445956777112794513023991125188,
            2045331969496016255571307687320013551853048491733214352646441341466617604859
        ],
        [
            112765822376634836986557327486952401905342511371567932656784212360129920193,
            2925784973032974919740053039088226660025084255241123579355659877189527261408
        ],
        [
            1615139200617101600744409619536119151548135245881789111743749077087127202607,
            928952548463900597431429074097494026341638502402888819595959975139532597586
        ],
        [
            89110835703618626006281975484745142479630710003689233432269611283359724860,
            215577133560624823939271084084157878843706221683942956847919314607432159969
        ],
        [
            2365204845648678418296386461366871427710672197784591168077970521383279482418,
            1305956795685348559654727794862561316677393382417655218949059817923691390961
        ],
        [
            3079404798552502156907780297645909071656015399012681371402409463283987518254,
            21056707131743755971547625076568417377953234492785298586731786122687871587
        ],
        [
            1774615721844036510130640283396354163953067525827829514432813052928446640946,
            2335149358230730291686085189834918003837685389648150105141235796252419309479
        ],
        [
            1735808336641971303276438949279976616427622212845904655791080520595464040270,
            1731419497051910986191800745158520013128509429166504524452212426369487243072
        ],
        [
            225628732048332665517140883504098234968194122687532130198116739739190659914,
            2967548981364742052624681942465301778302189310173531702492567780724033172480
        ],
        [
            799750724987433962024178782345988625264638811940430837962580781131993819643,
            2706844911451851414869588131946375233343117270234616506423955430971490523817
        ],
        [
            1369724618979165159567545620227678034464433354639639473366228046556595024708,
            2336720505293481339154253277307615910867992206313138581663759107186258146704
        ],
        [
            1930319710428527822612172469423758994346239585108798378474140896733181974186,
            3075715260783582884087648822116793974103741019719484227525273088977328650560
        ],
        [
            3338564282673470966018775402725903223528182579868287010100527892104759349598,
            3420593956586273983490728381161913171223107153319939485895365605089451302873
        ],
        [
            3555800392979470758767025620764223025989211483193054579480906006330657301837,
            2149899957029896266930433713982567969321434161670385808908337955713550175074
        ],
        [
            3608545457332454869249792272060591549043786202385519868035962077469064609868,
            2809440208316315053241747840271233428261159310708153434099156262944856645508
        ],
        [
            3322687396347671973732888070910250198991075315814763746941655084877070735058,
            832722278416792540687431048542953362405174329235971097088928697230453072453
        ],
        [
            3256622670111196871124104758094097761744096984947383503745643093253708235118,
            978374695622574912744133217293321822318821008760942454268417456141195625584
        ],
        [
            3410173130373258134073085888536026114751965010082957684030563699696697480724,
            1029778749451237919869173468746897632364581346265567722171293156697958069877
        ],
        [
            3112433780585229726581053697334217985356658602483885980524816220344484038215,
            2532342168888613388980558686859546650509221859779222781594186523997684356788
        ],
        [
            2105373184300453833566715269278756869308617438842998862447898598873739219726,
            877369785681960743494801702556244962845285506808792672979162666273085193389
        ],
        [
            1393232346062500558436496118495653473949473378263920202909352539047530421805,
            2756127133762923853208501814856325859087297216739373809908612188013181865996
        ],
        [
            2602735208672053198262611186569615211175565049926056251480233572878547833479,
            629329025417775185892796948300727047077553416972749774530835029538350502253
        ],
        [
            1793674060552460299974233062088263069538015472516735538751555695772239138820,
            3267910293235826685471049883722469455862230494501330393412138559038075359794
        ],
        [
            86863311610097694600007716574788775452468848027297474155593683107676444091,
            2437707467955141280580805831659061124536906723244797886865002980932492722630
        ],
        [
            647853547298757687427688341299451732092383134491816678870980494283372695378,
            3617636854438826076469516140770697015113683007543372219324291693845766252558
        ],
        [
            3334781490544017130581236435947958883590529475501049503331616858692678672100,
            1524104441388820711776621309003922630015731846383839927647934980171536936944
        ],
        [
            1706920492017425179811478489658749041569247255320747028220786202351882167016,
            3136062931779844207701097197470225751864670973511824570767144629934893764829
        ],
        [
            149961882640494348338043440935347934018050992098250101342463562074704074105,
            3512185327682078074777552971488882847736861539286017805546782388407073599152
        ],
        [
            370860151698809780775659878430714854391039795566897134502189484720213964480,
            1238632390866429469777130064298502868565198081327737370254478336416980048965
        ],
        [
            1282856472050108295483684218758047396436543346709509434400652555424465185837,
            3192157841056717224043634359360155098877589892941349993757962372268962797115
        ],
        [
            3312829654231446830533616425871987858809512713259532177921343043407846981843,
            1806976906510042164961209222220236480094335196359899499152673663644589005295
        ],
        [
            2826214476236947463134060188026701900955812519597178470627224598830931756638,
            1580208692732193723402036455390144043645806993218896764366725410799716087870
        ],
        [
            379282466405240907198946408283110293887947304133389197401888303636683398267,
            2678326696284237155462064013317839501356719176588712513572353629324338176024
        ],
        [
            523694191683203858486629087773330056719704186407500237062037916699142935895,
            2926557820959194747499923406515961933437184756076777735860240549085691053587
        ],
        [
            124833202191020085496726895079225667003902078587119506095688146305802394652,
            3363531045637590226091127058344713074476460386293564329053575414302767346399
        ],
        [
            2143651374532047414518845091756289685497664604612574318922876963772765730070,
            2673827034448835877302891179434422590334329367577351180190722501245625474345
        ],
        [
            3221138751067425577747344145841964056907436939401545122534796814786108536883,
            235336175612617006468583569743134666841147774340073069013500151038053147462
        ],
        [
            2555268812438549803835155012590418157639496654385486677760162898546595196513,
            1689750620936872465271905664884810894356966245587199342495604460756806777168
        ],
        [
            625234954128220194452646182586699463591457452260757480259168774898052708673,
            213161676086201716193087398992571428821719377385651036018131821081133441051
        ],
        [
            791204612818253360042670315855828265280744396446868065071639490833059389857,
            2903319472504514375570923883911935291656049846866663158923319947614657595965
        ],
        [
            2454646497469354145786043440836113873410753626627793200029667058037294177092,
            2032912288570051024788875629005185779516597292453270591316074924761292028478
        ],
        [
            2123337906329005118437052559658178011321855724007242277348144379266185921681,
            1894503378078529242131889602767919022671882244815906977803914704575270961364
        ],
        [
            3602877859331983834496856242375420741994478431198393391854598373337944528390,
            1390248307806555980791681315101366407220742869690031661994109003230157894293
        ],
        [
            639878381660983183381027433798087557736798886846049125326586828176785833470,
            3512419367912974372084649665826686824136068377404083433804922599142564888100
        ],
        [
            1419134474578125103135604337269063811149389272963545586390539000069337598859,
            2235806112698740444007125277529836633381483234992038997663439878202987160165
        ],
        [
            2778935883893248105666429190432349575416381537333107318387561120528861164061,
            1077278765722002922040368598422352116268480578772186030121792709039469085744
        ],
        [
            428120812125473710465911539814876147732404851270862105382572167865288414733,
            311433631492674653227552598028197969484982737235311408621797869297871619494
        ],
        [
            2952060790673513881810338872881675262252364545105524564508325071871367391468,
            3582199809541312286609332154241682748678754599041344486017973240874423950806
        ],
        [
            1594461313084220822848406979098581830091616974334911374972620995310916825614,
            2807125397722833979284621487977999302186252215199452982876117209095859541679
        ],
        [
            2043845413859332839989544551581949027414436310630598302726839258465898602603,
            1493460761394315567854883351837738680253927509880345067100858649883130457048
        ],
        [
            910520306205610055407037560562219297599712042011958124271729124108713600122,
            1227332044591912072232756174484900317585931037443282067667157281800895006658
        ],
        [
            1356322905904034407802797063629117404975010366322135572201704229186917875805,
            3062811278605169224008088325523606193685397687377873754697372903028059871958
        ],
        [
            2651699680375521157731474794703697878196552894539932179312542308190248741615,
            1374999585439430684113300998459982464172009456194373596393318069525504982141
        ],
        [
            2478956707907870604028063666882128463565422187569850243079631251653021026113,
            3484420957530723200820826205205389208856700316444106810018542093549855044781
        ],
        [
            2745165789654622430617796031383732860380537410258722201878555322390065895409,
            1389786264162289064932319984048404041828181018706839586582409596900469763316
        ],
        [
            792291068607630837524967871082697288161825884871154205347723150298096233265,
            1595885520235983259847467303703354388143203603602941324268342974672349807911
        ],
        [
            1112766696158267198974840537128095637678660084973877593826070735478819877428,
            76854025577946938851193238773961903814332442336300641590764677722879845665
        ],
        [
            3075088147214758449280318679771364592694228314680731955170139149431172226453,
            2631464825354322427832325664266556982858783834009349057603625173618876560686
        ],
        [
            1946952991061874087036397224151139450490763292883750208451596293164980017180,
            1671486844817988227846350440864329091397847162425205354534975696550529649006
        ],
        [
            447922002514491195056340638904274303849743543434622916451489369322819570022,
            481989665314939062190810517257104327416911189393567287995442516666694890745
        ],
        [
            278768424991728679375985793004023299002069942702077846697446381167229872879,
            2117939832550233574127330090850877444733498561141023361942969078992294709841
        ],
        [
            3216273780587845885344648641198104357960391646838456530374473185745790254775,
            3606237386675957259713749411947060068172141797816584221362457562749070134457
        ],
        [
            888490252135075821787230358754699355629649708262317489940736076372880196421,
            2243899191640238208431440104126936619623401575061085948377697882800556601532
        ],
        [
            1748762228708691375443278014066210232528543730943854135660867476022163374357,
            299810809101280072373711346937892828549469075660577914238588790523849116964
        ],
        [
            21800463980443581727936921323539002523916110909487141095813330024439604509,
            3239991592162948599965263758537867210199504881270279333333530879723254864285
        ],
        [
            1945649262091085266248324326387300230209483523911852369537103537534602188669,
            937547850790372496342721899405171497997439341142225383636485893081045476840
        ],
        [
            95187198852190497553925369717104578448538072022660253488035756790745062479,
            3284691659350683572361562338651440251050266476442725062173141352883841793890
        ],
        [
            396966715395293979183022035167233963473677021753099328784772352776439798275,
            1613322234499535439350563907086596802838800251144492804438492852751836971863
        ],
        [
            1705843197146248589209974041619858441399461896194255757072890762703413482026,
            2709234803093296173390529287307769438552461179797518815269401286400797214943
        ],
        [
            965896257227883986820160011629505229958129089095279852981573428580834882124,
            3222878455111086494470662906288505024631219103956585024274050126506278071618
        ],
        [
            1711062768895650467512736187912681238407905324392544748841566987114959619940,
            2037166002293356114375846587992164902616900087753130705770148512236761109532
        ],
        [
            306929171824313514409556697011428394218011837518848517597157431560368406919,
            2733907887575749650664983471979960087709811489243842872308868788028064963544
        ],
        [
            1589132075979748817708848065945386431745143428233530475552120730272187989177,
            3479574566456289934918449243936076329515058364276769923171744108995406563734
        ],
        [
            535088375724656896741944948092293887713409890408387277644439471611811707698,
            3084839991780046496389632054225148955101489706660124944353740712683200220129
        ],
        [
            1108714469400502294909191174424037717245383586375174474928489701713698780203,
            344696096736515166863459054453204973598183407079213029580530012456358476055
        ],
        [
            1896541196944951993777265586048099398652846183460110390523151621587553084390,
            1356944636529832014079353150870395726873584547194854259003641654476043751831
        ],
        [
            2129740212445659709473295068445927295211143686808997136843204790705829600051,
            2784093412242244048858451658511978494505560368170364505963748965317959330652
        ],
        [
            1164682312446525913981569213875150029132760939832308651498251601400403129032,
            860011516352836343688401715896426496333552023448545234232950198907527747215
        ],
        [
            403381603306414312665420204496598046512017134030800187206579847445734886844,
            156710329648174386978898329138661964114318418114565494873287202679709752521
        ],
        [
            3612709524322508414252878964415432233546157461869758422797096779080105910197,
            3298597797713539922720249912653326762917459398002362406667649739024691730641
        ],
        [
            2788472028266807168790808585452088947945831098822807970786023663768554965883,
            780984533356516602828788864429847085423068302018929746266555371946539918101
        ],
        [
            765015221711443098273066494715116075624315673921356068577773696969663768888,
            121864134634742875401471744901077698759842590065938894637311780483786803739
        ],
        [
            3420458059929261250134488209708428351089317850483628650712157545902459535082,
            2753073224523413466263788479220930266258909876418753081552150110011967761473
        ],
        [
            2435788601301668445647253094872163056944118800775256416712610409880768679053,
            600038247016283378097972299409314284965737590535869850167688589980357128171
        ],
        [
            2791234127851217827076638673185921990434565258934782489657649399234080946948,
            3019532625505810270756207292319968517034464214472035802893765165728566407791
        ],
        [
            2175512767988966931157181387193147869682253002700484615343260272758293076239,
            16356925783563920024655061104076219675967060212474163352137306664035714196
        ],
        [
            2346289056582359849501003989438672266264448907419687867675159268542148069281,
            269429309748271385175467663457270641975914217681440684037010041835530573698
        ],
        [
            481679002404926691230990214906065876613510532429501667509718578731645569407,
            1609976879746739928846288345159176310170130379856291476257183396230103110555
        ],
        [
            2127782061956380596600761098774414382531840909564578638354721422890231607858,
            3522660228464874209807741153414518456209790498657511195587886434205303653276
        ],
        [
            2990749966959304578563050621982841125682975201749885210174805380941485460083,
            295197603441351883186074553477194964532333406546643184464952640061744781463
        ],
        [
            322299859114885008311771586431338392030172898629995798709098486233393241698,
            1023285551085384033485966778701460844235475326250602612915962425374866217237
        ],
        [
            2679886206461898569320731641611496876582297592825799115233896892980598546123,
            3099565537546363902378775008459983997262715254411954165424270988571981464521
        ],
        [
            853528159824941445672647399048964399831359191507493106790462832690982526176,
            1009640753029626140011297690792696405115462988587033910421277684043461588633
        ],
        [
            1303674320335969124745880365084447847319437106063642511200542633107159295205,
            862053741658449155711084470286087651524720201941852653377417774320602998882
        ],
        [
            371784976647836509603140476112794524387140033126839183825485397106022337443,
            1481126947243599849498136670060476522501192641446886664638431717153471858730
        ],
        [
            256524228763970643322523560381608580385109852183329255389135850583181280611,
            406062519770964392170499110443173965524033961539587233636744514155485982986
        ],
        [
            889909761640899390466461648537512393214660407373609451150870536404743826631,
            3579579432590016439918468051553122806010260839218529712227712227008716479453
        ],
        [
            2181687776535382366933204874050926043644394510983340241902960182125931413775,
            125591469249575554746765789850870005842434420699124766244689384267560349454
        ],
        [
            1698011648746714871368937594549801676987990963546029514109897028714017239145,
            2032238188811755521211420251330988300583305301151292725000783151183349336764
        ],
        [
            207686199415566734810376310722982179068617367123996792470313948717972567639,
            1457942055660330932304294699096717861622662715626699977446009835743129689987
        ],
        [
            732258411798183046441278957122759122697038828507788948928154704288224686840,
            2612299176220286719934749375400756907183274870137646747294920834312868644617
        ],
        [
            1131610047798062548492567521656272602549897300746434874306725974344582031445,
            592276015836506844762700749171355258254203250155822561654862572344939966418
        ],
        [
            1683203479448902722167828838268483614879733285176640956474769817134838920079,
            2990934852576563000604264577641206566403815930150479384314858100664762791309
        ],
        [
            3379046363093840121427219819819164110884408212445336400953102193400631404907,
            3581767823598790218171818955173138326266037759069958949236204540729167542495
        ],
        [
            267147147550523725868561003543093307186644052136871409944613118661005584614,
            1306549083362239169609006162611383775071361663461903546405449470601023271459
        ],
        [
            296975912955049993838036596802334313092629826214334467025699377929310754375,
            1563707217733470474074970856533625421700727823760061087588764083345926207730
        ],
        [
            409930698864338128894354352383270205190831536703476012076004429065058122460,
            810813209917474447569624498205572650260997215620628649252215243057189717098
        ],
        [
            1244080118151222628554430592856097691345343883216811606005263269357031069918,
            3112961342564635769384393489844295061472524432493301559668801711930497029521
        ],
        [
            3287905561524106163037657312076054800525947413789669708058413492038554328847,
            2950266460046239577741220775173597014955783375111361479081038783371923101261
        ],
        [
            1834667074444753359896291977244884324984125181165619220523638440982002878973,
            1028938841439025536907121844571940895060940730436245288628559554616030756654
        ],
        [
            2696579144808608214357559333220835033277874753649087677547926288655864862396,
            1205667596625326964488748126939548850792621845142605787353435428502428194722
        ],
        [
            2681502303973249854884858344399536104286034851010362500805472440066210957701,
            2090624297500029615299510863468795665118802449870439334493020091696427901315
        ],
        [
            1353314499186573664458206377062562808249080943135426913783009658343962961481,
            2765083962822990885404819840064727313062737767044627137615530427213920746301
        ],
        [
            418493206714369123577433462079076010029158131200185602134250755432510923649,
            707998386543299716720343491204719022813222859618895609544390001004782644320
        ],
        [
            994749436490026363483216765171719719813756635373513071896945407046466009916,
            3542023359278349542922434792313919575183783573969934645527389879728870323439
        ],
        [
            1890008117079085184019219906457544800392678580280084811260498224586609070286,
            530233764155506684122011374141421351751148778529665626269052967779624308325
        ],
        [
            1380484666773413147984807138259355829485624671596401959499503325097178446404,
            2703143567161792821055257608672826415980743659971254233408855036509811875962
        ],
        [
            2143881856351418759124748482049358565778910428733836748398777699149555891034,
            2186504045350479968631256614333785165240148508469904761831572298072325147795
        ],
        [
            2794147613012298673104841054632587797837325721650333247952170883643570500710,
            2613093490820907283519815366146280477230890436771830509953858178043843459008
        ],
        [
            2625979094712716243539648580331695634041650060241725094563615224537054056479,
            145143322058807873791926380354826174760141531075716146087195666113341406100
        ],
        [
            2912042742810958222559628370002186243459717464446177149380721928196350211880,
            1095311779741249761721276459609161253222688862762095992035499286908387724976
        ],
        [
            1779688139950750136680613010527778524901137919784933323807835083178662865397,
            2443673470483539351187560062972650745287069240410986822268053157528350814229
        ],
        [
            2131257578483960220347030216154712350782825143774667810440672905625819556803,
            868491622632592338574614600558827126185061061280839427086037749491272636942
        ],
        [
            2219005280109778946483442325473674751018277532855518690831693876689847358912,
            268228073082292114390894552479318098546823436290210690954657472261887508233
        ],
        [
            2467777871565605588821089206361725030593121231139954405293743820019316429337,
            2069991336503010889436721322920702620510647146193316568814112316083040831176
        ],
        [
            3577501695097063979000880929536422727582550178446643147830010270693854635348,
            2035294884291881522017348441414523234930446764971044277218808172917534058938
        ],
        [
            2916007638012715951040881085223392656327753091743451984926427831539302440694,
            101999113634064710169079402836107323839592545174054596535848670931124794072
        ],
        [
            2824482828379328312126109430912691348039395134484392469690037535472985287979,
            170123149569960330410734287368175015043768931496132108203420592659991682297
        ],
        [
            1722717317273017311710033441508078253294103515222910371014974460548425614659,
            2455794982320624552496521720819953146480298894982220570859668985011878438440
        ],
        [
            3323332844428319232630841298737492488606773387534937061908049192786445054249,
            2775452603532873679877923100539353685218185462328621498382613902225794012998
        ],
        [
            1608012153975591201510431671483571431120513181059080848126129285407754084748,
            575592304166370707508545110070168578909474113291472127326388774685581172878
        ],
        [
            916809345825028426832118427347317839178426151786124666474024597549724310957,
            3069555112506328035675763181932227894553434381085323151827207060709357462248
        ],
        [
            153560760075250381766471501226441998688409013753252062800770032940893580349,
            2329038724186047986576327612748573076822768420981449905843361105210433443270
        ],
        [
            2251563274489750535117886426533222435294046428347329203627021249169616184184,
            1798716007562728905295480679789526322175868328062420237419143593021674992973
        ],
        [
            1952032427782133959985228051054870623876234309599006856796795466237953231448,
            744413679445899225088843138289996934867918835619653321950444531036817070023
        ],
        [
            3162883296795762041497700357918312017339509549159370543230518526626437112653,
            1148816493574468887215135074549621724232310091624566542087195747872792868322
        ],
        [
            786950607934610388520508637842877731308927224203614303759337398330090790623,
            444134697710380413360573180457740543414390667171294106626775858829645857259
        ],
        [
            2138414695194151160943305727036575959195309218611738193261179310511854807447,
            113410276730064486255102093846540133784865286929052426931474106396135072156
        ],
        [
            955835104121335308947276399583596848959851821452355864667907221325383590383,
            1935683370537209806184243406809646867168041420482463925534831987536519170687
        ],
        [
            1499611007946205543199170798196098786940176368383871138867689500928607330374,
            2662008410012406974490205380527854666032675717377005780162761284021647432331
        ],
        [
            2335197826477933983066242217922654955176345813321200025173943441365679314150,
            86799141726517067858463816876244730494086420214168736349361077938664862865
        ],
        [
            2426305297748003258516448191982872419574201776532744568583614742711471397997,
            611146900843862661160935598912412637915904741887617221933114742269852367033
        ],
        [
            1819742747902080962279305391799448622733402573848283520339621821028260796959,
            1894241144684539746894260685967399165405614901992249187163143950195275701901
        ],
        [
            1566900754533300858179807012858131246327928750222566819288909586499451206334,
            2323811598271524355017219639060977623543930469383254150460465078663134678714
        ],
        [
            1338097767250711433700785616700918851742529208514529951106274243527927831096,
            3601290097662913510540208850467494388944371519879253105483940917906091319433
        ],
        [
            1683076217460316609061101548674917172577600596732354862732552514637488814573,
            2586296790559369551539502725860235780473467857462493373020086667442440193461
        ],
        [
            3470075416984304553645258515396988848402044843556043814143694549291509194436,
            1666299363887708992239894153878840011200424023864139235605837090808931067390
        ],
        [
            129884650079435408471813606095297277059523238954518094473826756223429238429,
            913031838387203882010246435451325905809656720680281880669305438372695953289
        ],
        [
            3445652480962486836667659474432628384578750077745289335336644514805586651762,
            1741653654983215120166402497338863916929176017304303902363120840611844416235
        ],
        [
            1173074699967858342716736787366933102436976281324119440358211746283473098092,
            3075964035581410146694612776964161590283242001470153540218734715257792166291
        ],
        [
            1948864707183825487572530934859230839519236819821721157111541446530257224135,
            798780108424505404488913172014962400148988458061505603829909122085722968572
        ],
        [
            3165333849798411161138142302194551326502959074734249886012073955960267320358,
            2854077232678939262337800847761960471531706329482426572081757005793264065021
        ],
        [
            584219684922011437746073096716853840728059302768805720402293458731947997988,
            2691605392627141392945611586058726186445966055416403501891746673585009447073
        ],
        [
            264865088823397344079537851791331047852344700250947641609789815815437187715,
            856557814156118883640651140266045634237123586226962432863642966399740605873
        ],
        [
            1212105529543873848411369707567547187480526619270372944387195134251016552437,
            2552579868998151139055870387891260255591250119487805856658511804923635744103
        ],
        [
            2759929251220121311757096521396321905172783069804137943187241377410890848589,
            1013388642776766405334075600441854256934688539631486641630323046104523794325
        ],
        [
            3435662243060467637677279408549422366191108299439077218684237876763341810879,
            1206100200764686560370450625743787352415337337047308087134628700539206972086
        ],
        [
            1977901254287550894956728572957134897985203087357872251941076511047285452123,
            1346842642356348816775497637530312996348462152604627197529080983616576235485
        ],
        [
            1581907638985290987975047412112008678916597048367684526184099730550194065415,
            2288246533671252346247687962179397967163408912494860510981460961024159618572
        ],
        [
            3215377452673680185835021004830688268079390648010676635220128902519168416923,
            1674957009593589739638616939189211577318542927235942161494800623173476894918
        ],
        [
            3396057617195027713159897957858092093258826926757827467732086865786377444102,
            2403568170323924513104032431512050355627094479417158474914772545814875796054
        ],
        [
            325310856310207888841271598900176645709547071516271373679357299878055669525,
            2861677118910432905996905108378731982262901938718390134034663016688312343427
        ],
        [
            1925427404573041560549638633971822727278056640694873177265388259055141273564,
            2149185931265263003264629477521934555446245963141224065368283592107464297049
        ],
        [
            1057655004272797062633705695597766087036831552982842977913880603549380151466,
            2130130885627581719544847915036196574607634081790527579681856058518350163936
        ],
        [
            1786242059890666469307365196518174814453782118901787482186686744245818012463,
            2172680482993759140271167348144713503721696709986572085951066664839388293484
        ],
        [
            2592525455921742135918400168106149306210970009440868747852006912674191605906,
            2550305630907505809534995587257079662509793820536464892848197484572098781014
        ],
        [
            111752568734708072011137681957171091740064310210630952635788677462490949489,
            1966538689680059826741582906363349945575114015419692615822155104740977191321
        ],
        [
            2324264192758669920944928844116594735168711655659168025211571634463212989215,
            2453209181874565651016960427707879723586882840596638134526741863234420038217
        ],
        [
            818792252748214652222203568101444114842946877275244081137505104552993989249,
            2471135473251293858404864644674805198948427457640609601515835463680395027066
        ],
        [
            776167224210253175836285301928858826524230272765386107941590743597167238720,
            3044593275856778999572277625341930135050598088363464944610781758478552167560
        ],
        [
            2767418361596469194389897577063980781767359707916121685125519618739970163355,
            1124183356341334924855702050560569148670124301541230516023323823985404910253
        ],
        [
            3513158900447819618700445228863547036694626890925843610953740962149603482734,
            2038286698090839235054970774714871346106378670221757061557885786099548421055
        ],
        [
            517681831514430710817158481088000571456636089484182444914961386383717794582,
            1459737506190708125961565377404508114648445797956698177580320945537417189767
        ],
        [
            2764450063359771480330846034975350106048674448417446553801535244886068866892,
            2500955915434901122019038304617790171097079017113487693837548584032628559083
        ],
        [
            3184601066099193053823632069416872853499121524829816523443698520118638972221,
            111399286855641690694757616558822271075634785548525857820633539322287438076
        ],
        [
            1861764219607632476451968430680705159045765477029736548085454909942815526303,
            3542081125583459227861063385092240523576730790188055012978461087647652048846
        ],
        [
            10925555246854055743289295413923076326390541878672074284471241830391529976,
            810379063403665716239985697021625834252465819699617633253170927366131373937
        ],
        [
            1925469472110966024666451107813057200428670133173573112269655451746350245386,
            1187189363484828103108277567024110279560050728332792104397849042655830458502
        ],
        [
            1257234032480175630185580604439948675879173824493927714083831311549585046766,
            482591378023150470327639933521764621888328430410377343971291074047537101431
        ],
        [
            2334319993908953455700110484178707117214967972232088939662977870360647156970,
            2818056499399790981578195943345246458116384474394556164088380917912187593212
        ],
        [
            1453145677148250112321822321443172335864030607730961070308740138762391252935,
            3617981792798631412887889951712686522258702128207981768326584469873932484754
        ],
        [
            264643236147417159992044802699391039945632102423375233223220671619422214434,
            610904689309149986363589451581676922381464434446910426922817060056083567097
        ],
        [
            2773555644105234303846021450759411618679442176305095821653566380427481880668,
            2878405667973852006171581845359598408350517329366546879570244783921286317021
        ],
        [
            2380074631138752101437386328647668302433161481157298955599519485146473998414,
            2940162033501039253058405622329360778854888527422589401316007987697096499987
        ],
        [
            59923324335814857005652966889729706976632643533439489239403033851211490829,
            3181196819190011787131540430610930324408745638588775047528706552833472475080
        ],
        [
            1571134397970145634572604253962346713191790104259693653437624133884723196915,
            511309416166810662427969443722895543878733742083314900009440861143766415361
        ],
        [
            21090530989878836908367190554625378531500191692603997969723554269923877778,
            2771500794785272828011587832172996564585508124740321638858260733779070073032
        ],
        [
            621303564182234060808181503818404204870407855544326969616228975404966772646,
            1381758119149546152274589114806432955337739448745667222869629159555498152415
        ],
        [
            1603367875109750844401808777605019545782079142993759227560886400939494569928,
            3404233473008527201696274593235213333767802823633271526617525914604458121747
        ],
        [
            3064432839007969661251145008088305693584410819966794512614368597856219962482,
            783256745930834086288610539747908078655069214006352981421868494072213571354
        ],
        [
            2573509260611834641929601495624663326040450806493971688424856342734838037808,
            489632329414366712473800098158402333281555035744201997032862455100685111530
        ],
        [
            1373013110025567380060459077575726370083805340382038749245013725221282327457,
            2271658983436031571764113689216829854166985975189230813662757962593273370705
        ],
        [
            243466876262712870310499646879826213360676861126171299065326838396697300684,
            891923608292171984769797750319491387015995834783589731015608767716778489152
        ],
        [
            2035465927594189567864787276274121052811830838707542644166137070067107322500,
            2293243214098049976425980695256140756537564052456935637846524530699635529072
        ],
        [
            1715507122267435124880907385699722499007841543359383748906967432836714601915,
            2065683622001523424317888964929493250974883654939917054448293842930286201120
        ],
        [
            2906653642813167415863836383642871880050990532175816005542735996509246708445,
            2101103582375172516655999605681405804159432128657161521495199065707274548843
        ],
        [
            1560478280364678701345899621740888632653158026800096320697331299727453323955,
            2502904681091262932533150924633878024793617322541538974642118205130709004124
        ],
        [
            1088825136235742041556075285669369753699521218552343596173215811771470309575,
            607071558939135607706029375168245965172230512282049740495005044883485254652
        ],
        [
            416480930348830698091647060484670913532953382502409400899099946640850762655,
            2303434329028515556374106529351629273202094072128674875449835104642893549223
        ],
        [
            1059226326329269227798760274851746346121838934144866840722833084379215695718,
            455998255867283640545200132173274853754233138086189946906020858549998434504
        ],
        [
            1024559718945017260657672873923464530437289768440141950557818820996778411842,
            525500033723589597309036453730301911712422803406229661029628208639589866511
        ],
        [
            2056028306188984024699016201885443563164872865972667060670091877117616276834,
            1419412493706512914027360568510428136300835377049697326470468114560769950308
        ],
        [
            2521038744059190227863027780309672155134248925803510182471085885871826328010,
            2055664921579551707407017847075753140537141245184993747243302270696485943484
        ],
        [
            1408309654797092197568389828883985051397496347829594535681640019995307652445,
            295921513421790144469734685069951228414338437813405505294106756210992032229
        ],
        [
            1987857595984681386153299845716030466354725651174836127615155461210837869564,
            2293923060372667346124288305276256569940238390418855305479173407955750665287
        ],
        [
            1074973828105956295697455820943040985586724095278707830076756602555601108444,
            3326765437245957223406988059616777659852354773867298474672160569379624598430
        ],
        [
            1401862061794147305806657568952279890802547970381675217693442582127912005310,
            910058274349373118447954573574441457656632333180366570053619401133150262813
        ],
        [
            2040966475187373851921668684777109791068677257197750053913982531497273133975,
            1167958332666304570814202030094477634345363022473150543742806601986529818461
        ],
        [
            2881780782119017791457583552000797082603415839437706575588805401515980505801,
            2436105237174666086889653702042028393653105027534224748338553775980791489395
        ],
        [
            1138781660141971412207137170011812332951155719283266572057616562955205995829,
            2657768812194147024915418195050409322486415583242017023943729410483676474626
        ],
        [
            88581112279530612334542943009705636136002388463681106693549082166685838725,
            3496134215297708121790719225608456452574651558469594407547800088961881026765
        ],
        [
            866718519953191029204822844477480603275933535155329865978768093814160529674,
            2022882774094084071548678749116103222489874860976240925473298660635212244802
        ],
        [
            1103918207045639319456460136379598726437052653753960546349780312287131158223,
            1656811459960430943611479537236804458740132078453755963357596576700576629867
        ],
        [
            2975764785119134105842544511285384981490365867343400021422469912399500877645,
            2687980107817591862475555961986751017099827078208385723645417765552791682099
        ],
        [
            2054447365318177209738241671190147649701574355450360479017715224292009927393,
            1227206940403531159772964107232373497220530020193348767638035040017379885984
        ],
        [
            402275007431361887464920597581616397711484740464854159502779178788056390885,
            1547405786479003871142635515616266099578579586990668594451288428801472362903
        ],
        [
            2669324117696876754084336282080783960314916540857113798726442554388023656184,
            3074286759765067223595900394644532377637168990646921851127828180794850850636
        ],
        [
            611932396022950536967338459506782836623876614969030243077175645873783092390,
            2986433254570022449958119232739190557250941610456904564848292348906028792067
        ],
        [
            1110995377995699045828083953623434494450657345505392977032896710538879544144,
            3071470793346350302357608763590610007478960895381257765814531991563057030742
        ],
        [
            2191168535074842056167853224940102773478321048031820308130136731344529117475,
            492617323352024208418412531798559543092874332708570994021422823607454559418
        ],
        [
            1818759115593575585308068448791508192789866090941451793170759417890828490762,
            1305353903124550364838683686338031038285043137449345518795766390174337151903
        ],
        [
            2631013586413722723014078756848572110540232554858227410413816548047325168051,
            2105417412111265728359541491742019675861543959418319743611117424131871073867
        ],
        [
            494722738667200879981866755759016615873180216451714847099458992922362500227,
            1539404447578224883291548288433633968332223396361092124453992010526489574088
        ],
        [
            1894316435470914382555165707375744683572341270069865836107052559173764639667,
            401287370121559774698743821124544382770349508247396498174321596110198582372
        ],
        [
            1339247525522496394127023115420380868431447741930632224270989291600289579235,
            2330930519705316142879600410372647788413471043363313385713997026124191817517
        ],
        [
            2320587088454453474461645476206103420492539243459981382841070259500342411471,
            707303545980793210971675132996162637283200017126206538680628878370110521153
        ],
        [
            2377659897024221375470644518744478788982138263672700674443630590978849683809,
            3419989952269036538781036113174387172326270380530270982346793780460729200034
        ],
        [
            2687585515362755421896341880578567868284030156693703993329134509207013359293,
            550674138339341111775701426337380778844351792663711912206724163064378058172
        ],
        [
            619785501193479957534515714310017569776352132000912157061487205381157886132,
            1961366910419378396302827972401933597848792446727660497590498798601343853897
        ],
        [
            2960597928226130798805429646261618976240340007412692237798738046399566677924,
            3508695180344311906202946672427154710274134142520774461776498819979015518079
        ],
        [
            2926849849449158589418504157622781316761588577631946629896933307400237548255,
            3579904677936943713540587614497052174139389714845927197988064028772422409729
        ],
        [
            2528266877173878010055911786705258188545546534139599446181068037003246641972,
            2090593124885859667054468890302718556366617309852711480847196828672489780384
        ],
        [
            2444375104485440204606531945078810145038148666393834678853843328800784491413,
            2715725794432857257355582195062001572910526811270194737205485553709223325149
        ],
        [
            22830464908174189828089916657865484119153417213263588787115884234394820551,
            2144656372197073668726998695697011727390449826738494763726208492934675687351
        ],
        [
            2160911736065509245304608365930348966695110267270046309451656634373627649798,
            1163682116033125825657519424156769471044453229066709940373641637423931934054
        ],
        [
            3337375727076925923347860860990507186997043901018925752183704995009780982617,
            789849303430659746633537234664825369690245855962498730835768457501816445262
        ],
        [
            2716386435720211080341482697862373973972358535390181213762877306777737012402,
            1694833211852186945995412154030088403536183890500755705683031155572812198349
        ],
        [
            2068303401887779893147375033717840031634024130559056428854775490478246923099,
            1302558735633136858997628501160702103360976241643583615145118788605800501823
        ],
        [
            2528669114399089536204487719847492540160633221112006566613245017377953815975,
            3355482321728480378876070603715444548564989647597270339584107783929482403385
        ],
        [
            1261599618177618962793920186597687295419265824130061936332619302494768478919,
            2783617516834130711477034905360493329011706287809097673216506817763076782638
        ],
        [
            2296010137652334615076906848600702206420819604705598933314103330038064507904,
            593137988508667983800537181778974626700843711375991890922024569808180330689
        ],
        [
            3550068663997426488921976653382588625011435366616319009448120503817895378028,
            333410037907206817306890788780367628702748092247180262748072669817226553712
        ],
        [
            1578244233650262393441190533726865755228496176869169339972883019206417143875,
            2916675240291132751272523072177820169167325640678555998767122677068069504203
        ],
        [
            2578708307946151727285356080366654771256622596667386016883098096024764936468,
            3547149991717605187248264974055140267141465574101933313814496584854066409070
        ],
        [
            1067242594064079501648168388172061910333397472745655832282853323030820063843,
            108409220808480307369448490727067533487994293376444700684037781053298403259
        ],
        [
            1438879968873284678993516485008080871992105419269026450500135928583384168688,
            333856453999414929392413408589358932084193824353874579187651515313020359769
        ],
        [
            2085247683945044480852971266898030909967072967111091473808832254928660354607,
            2485835628881711191910958556160457454778996828420985267633930125611726115768
        ],
        [
            477210647966136763919276861800763093178095337893692383194424592690231940061,
            249607430987277999234526517540164575126654109544108544480054797746736570800
        ],
        [
            3439303457066047146897968415062046665605853275226669283725228224973410585910,
            576124419653395914968187737099874519814103127209134795696921745172483058236
        ],
        [
            3028687819239678122848199946542573863395992135514552484651611678970005763129,
            2961643823025691121513520662201781259179479037567198808346912150041025760642
        ],
        [
            3217248534103588798939334232631337032410025788470581973981396764231465681047,
            2382487873308676654385098962584563887276844064402347832716704744043722784812
        ],
        [
            70223145378785170243702578121178644986245368450401326703486231450287863627,
            566197969536520322901287947074318556204558945230303949390810423446802406323
        ],
        [
            3028144136397350722039435806065376945342224221363467830775872476071042099596,
            167098690867154485139002287996988541908068352838119188548912894969546326088
        ],
        [
            1424858530411014835161893358951895950005600021438253129735780882682252689593,
            2305727793424806539572292293130051301594968780927626275319782923070998204084
        ],
        [
            2137513716516327603808109201538743935930903413061745351331773762548511760158,
            1642530299556920094344308735995008094003081457462443723760327041776469019076
        ],
        [
            2170444911584390774802338541806841054793712556211735475250435550223474552592,
            925789261675057834371037875523035088704965828465840628994713637520457333016
        ],
        [
            239299595833165228919005931278081722748571104921165506568868902567605074538,
            485001543376876278371961680415603784960370504830892419674368813289405424875
        ],
        [
            3080380062043844759018736411849858262358110468668995639984779021951968636078,
            2402265611218391177266008066876605247210502592712781467199097469773462678225
        ],
        [
            726523175548388386261502324171774291430220813407320118077006064537560392330,
            786330320941681238670628195289980168691286367143496676979339036480301999376
        ],
        [
            527181411328890981971052946489613295601720332326053123212209359114463976205,
            2153641849366054831187204654204168306183349514724183599886856681068048360647
        ],
        [
            548403912567710249138395852931702442214070304260935779684833978128636533986,
            1820119432165084967589110130985988930607430366654346658826186881340393135345
        ],
        [
            1055707400443116102787479640936967686027177253722371245083270825233659393085,
            1529404944427212407459549740446357844894249706911152782301314430602619804108
        ],
        [
            3604699563774018613013478662139866299897364136688436784910471089709564771121,
            1877420639173665439817870412707771026257151154196414247016132896387470215862
        ],
        [
            1334227623025169197188407571635794051283637310231760303667085410581915700021,
            1949877078010470778680860969498171171122335730952599024624803418631307495103
        ],
        [
            3308762084022080981421381628996649710517264452719086435874478919169368804715,
            2402101985509711398701847117755018203425777675996940000965112623957330145868
        ],
        [
            1665881871958289138802712383541734953129067055326286239727041865486531283570,
            3616247644667366899175075134655397038478794588048970408476914992988017251161
        ],
        [
            2112164335316897143532032199025725867588905166012009239598709182355280065515,
            2825402900866689367007140167090188180425426910788355395313762834688260248117
        ],
        [
            634951525865404702868066023611980901349684561467873427882470721637495099919,
            2178647893306834053326446190201725650048611097288227403773599186740980976285
        ],
        [
            1341178436815612054719172387245100541421209962514061177862693819245929984135,
            1326643103813011222249037873591741605099080649257821474786188634904101413693
        ],
        [
            1928710057077228449920040314271488497108943704097705502064531376997670270931,
            2266181469128837281287656381761672050739367882500404480638892977272852366881
        ],
        [
            969218608841843132346322324841729971529593954176078767277133720598489668357,
            606900183168454040777559974758602149603502324650244544303079399500690042393
        ],
        [
            2013350832011494097843192023013584600183073420263235866273101164869312611708,
            90712660236563155479754789398598402903732977477056735001011271430022436372
        ],
        [
            3396976507268771940572242446745957441443927281190120339106378150765794683243,
            2412741837818252081470894623640222254809923360460175760983381510548136273698
        ],
        [
            3606409001635563285156761927226165887070229114178147857036216526058311335249,
            1092396833411428890667907446500502751825053988217814009934347833612745642070
        ],
        [
            1544923824473254019116239003129558626125362616742425500116394033599505254529,
            1465349443371708061238467795142261954743713344644799596216285990321977000373
        ],
        [
            113491804090467857612125750322844575213787440679203395630526874638303077885,
            2028057101479207102461777655354995420997496563459354054546268475793811643845
        ],
        [
            1652495545845371778467883968680026022222422089600601509520876233591221298667,
            1257512680478734992352959448953843834930888651298716349936596227713642044718
        ],
        [
            1735132339493184243340725542423753987254833174769560101474361526571946583351,
            27330540439335548628321946448059137005887875330678118281933391074303528644
        ],
        [
            999589601024651596708840623565818878499651672244526787051482333844246243941,
            1556707544224102520772713942483754928174646286011090264336584778980967757013
        ],
        [
            1681312560856804229526683984753830811943700510863269888887897515341932766251,
            2065757756192665992865056781757244443742379869237378116242523960469865631998
        ],
        [
            2058951870735992982026605733702307208101813514180467857318656495202383185176,
            3268996299695136959341188422640393244547564085474313632107392993963324140014
        ],
        [
            2056960676848885737798371134589584163780497279931334671919866051948581811168,
            1741359147160041371302807510240561900995865771279421888187249838945794238723
        ],
        [
            1167002070266749840825005896490956016236165528302729567545471999112944906391,
            724716405138963198014997547695908810889048549156514080027596147160291370305
        ],
        [
            717433242268160049163784137690479364638414455354853503549047874912074602102,
            1548748206365927633434472413810887260565959748266730133832127499425371516599
        ],
        [
            1113770395880110291540688660582111108167550152891676896388447618267044770699,
            225614903467949057887693353344008462684737622787852941160491287904124662539
        ],
        [
            1485058593675291436770632813229171213081600725926085342541850536046844108938,
            1793621954142096162709529585852653649155672217087744074142012644930653464937
        ],
        [
            3476670695984120275482827092638881388770060638684248848714588194147006700081,
            1886524232365250879956678425943479251575532912879489640410209691903853633501
        ],
        [
            78942502761918568770028495237440346726648682399909104284710887733399086106,
            2352329060006211734866796061368085624251562468004096360671974444953215839619
        ],
        [
            813411306209308549231686755344288448950826770557611647490856063401538266082,
            388260357229176651922921451505223699462456291090208287248038895703757789197
        ],
        [
            2400377653395741560762585517571389386824872672242294297839787377212513042206,
            625963574857112775116550276725479329998557438550085741821320481021022314633
        ],
        [
            2328311306030212189043981540771838515808167713931548944984202663139515716155,
            2492267419179473373149177460543961766435995439950143787911026640253198630634
        ],
        [
            2387278462118275663019682655223568758817746496473668610784380666316276847549,
            2366392912056517351075178537570019722508034279024404671859228940369425653110
        ],
        [
            2114043901163989266960550512790503188352140805965143750858598214845925650606,
            1263535257267454609784459072919175411484521178579707297022413088083025242903
        ],
        [
            59742145227906406483850036502479681434689473008676866553687016399244912392,
            2542708853923609004067985135730679808561712875491472740521746862583772210812
        ],
        [
            636010637932045133320800908704730609314370804715286131693312911610589568614,
            961184011917051478754418596971670071602153673068923576248721877819369343802
        ],
        [
            1385321288061225556756217710115128107797163633073592537851457891527164069955,
            884133458066727093516473175829774361048238638693699012568518768170315343692
        ],
        [
            758367055389438625364170431009355773885665422613428814074753204465381568635,
            1297727568042288931569138891121976026502156814623013130863114577102812764955
        ],
        [
            347250288556045883174524792293804631653970133899259158293492482097831569584,
            1961316292966031207016509998947408765986081794211886403901120755246344327975
        ],
        [
            1618690143706255801807773941554549190817935595982010405820190876061657720006,
            869166062594354289846899813362309895350435099932527145815122092397979607037
        ],
        [
            1838634315648320098377933813041132543577219555069642930639820023291216325415,
            1529983605494771676066515349178506396294249260663468133203781588859819007226
        ],
        [
            1605761809110472849967286703249646269449262088256390507097425667304759998260,
            2778705695237273113564800057362189513234607857754067598956643514325456052945
        ],
        [
            3411908887615707635377666445857046055873541270252857286357865762696431003144,
            731871578063282896385513070338640294885089868946599519285295305156675019160
        ],
        [
            3087826179342245618253320870694339144383060104280990174148199503867526625383,
            3491370412646223145431588455284304413010853471815192082926914611232193577659
        ],
        [
            1436482751270429389743178806038120026461471807922309148229447715029903414786,
            1666868445318653269944338633661851246179662160526363040276638175667354338167
        ],
        [
            2083331818739824497741363579518842947887353398223338451239015909684569222581,
            803732308089347618300580814078570019393110433387113056533917045601819866173
        ],
        [
            1333165738767294811324643473740459024513360282013848003638568328453569807861,
            3324872774354633383424936425649606578793830970593411555017483797025902771350
        ],
        [
            1701353517399938600269579188937389421636718828509341624534004474699861544304,
            982045252370486712463601150815912589800926352240648829942255288306435594694
        ],
        [
            154403491180633257693040438747387470378033364863415878175486169393433469355,
            3204938488959824048546277939996603027140231747699901842459271581175521669368
        ],
        [
            723459534533890816489433777735842913898349668429456824296910758117461179034,
            242799587564906089500242560200906533162881507520621156475321851862194708981
        ],
        [
            2753553332546729968386491500304817162737325726065761497175967890302687642812,
            1607942131855693595003166153590488091960419143993462584570217492975562129656
        ],
        [
            1318380449900940858865061333131606747009833602974109493687016869645480407519,
            824831465625011385685225132275899244334146133266851046834317903702436443339
        ],
        [
            3406605858133553361333265720938744225870879664771897953784469453809670221140,
            951771439755520751413184037659273661906475899204291367776225253586492726939
        ],
        [
            322881185844437667428941222631269048437916337535492466690110884912942662893,
            2408973683372380251710642884281850709418801321112976394586138388159314573007
        ],
        [
            405651299272338889177305609117326577035390334272323319632791541534976007116,
            2403189350929802616202215631814070933678092854541380504903809068323291560762
        ],
        [
            224362689432001608162440684107608338550077679080690583663897253625637368804,
            1089475930411433192334001657654788489125032803526758217361824123802939165263
        ],
        [
            3427005033874860450481529297496326414099998098069008018777339291027217607772,
            1838523767315535107424920135038015356690704952046462913411177863052889918094
        ],
        [
            971265369167429416740822747897568727646706124584943344118217646401474769333,
            1841017974237665428880957941884047733042022771551566493876831131552515616862
        ],
        [
            593870383382776876660279010014844606756390978498220975404532129561707141345,
            1686799834245885653972636115594234495471835994524713453126028613189622517928
        ],
        [
            158526420068961916859457596090914564342752702816639997380569526445580395317,
            829117473118004491391038359292216575457137041347974965494549565557957856696
        ],
        [
            1145779849055685339419364615770769333393499278335670275163049680913140509683,
            2788919154400397863209918313477978879516215345298341199550275309881538159925
        ],
        [
            3116362794833038183976492329109547313095843900691440633169686540582464014059,
            3493161563205582068593545591027301392887053692389997071622408416554079460959
        ],
        [
            1484626752109997960148427439402147978447920625565926552692192513400801032840,
            106197164952655019784492783946283241349642545386756801239606388396528838557
        ],
        [
            1905886704700624859591161108842694006068401527337545253689518506514368311453,
            2930319791340393503878111037261975689788636509301758506631633748789105811524
        ],
        [
            2520975745491353699235764487116637116999082965127347369976279028452140192996,
            1121629571053704096076618751099836481664435087676492791791464786738401934277
        ],
        [
            243197297174950489047429059272755382647269925832357483684904121385442353161,
            2417007034799146494310932386003928951978739444041601103686030150489540099099
        ],
        [
            808704503940529633042533527196170354739879165235854099335954018048090166094,
            3250069164566476474875427019235306310423414676070245668865855537758860899226
        ],
        [
            154229390082782874040656704404635500870072484057583506571360633170672994819,
            2702580522127958238752043600053843204107536082922189692357192526470020183763
        ],
        [
            2296876062395150663198655775945704456626070946553449162794630784785525562017,
            2954047352783324167659477602480890942097095078541501369002104009282407983605
        ],
        [
            2369843936932443670822535910120393374869045918271657278773939763527759009977,
            1504523220772650882417075434754212591932774780940943124208852030753505106366
        ],
        [
            939818528450006271533633387575035651098636084551955010694000346778607054148,
            3288036962429189904257974342922419507417520404552917887258043999949243251337
        ],
        [
            3261482392020733556192001297773623607067547108643955544388526649674482826812,
            3591646574338256506691865028073929692592246225874807859597509821099836701353
        ],
        [
            1787025500314509707209621873912066561653490978360118110526034359358411964417,
            3421109838181987883898563834025345980326698037134918112926105203592921164968
        ],
        [
            2311067462891595099991833582046690970468764702035366824733716384542858538356,
            470591103372156288650571624843786296549423881481598013229606695835762897581
        ],
        [
            342559482224571965025189023541087083168706464251790471061097523992515769052,
            2368202754453331817392255123704696636258753331639084720511390832405023708522
        ],
        [
            2572444430230869831563822697183525106374829659556462575156759807443152314062,
            1629527166738200666038465328035159152469458766421654684492365855846947518815
        ],
        [
            1737389803319738463977618408470915902963778725702701713925657991380950954649,
            607082767712049126327196794168950822631607164722155751481706035333917604213
        ],
        [
            2871556558000552242893836092551691122481664492915647218631883507493547887264,
            500384672074954803514661117946887054859762315512424468765642494189718439748
        ],
        [
            3461109898461294404913712148331642005392308171104928758316008253448940997221,
            1749611977268851605988230236285965166361721258988901681470546570063157256891
        ],
        [
            78615564253467413638171585726207276986620474184921384429093571227531830518,
            1981471018460691817560093727855711117339515783816308036046814473313844294189
        ],
        [
            1474473102515930508594064469182212180992913337870765723235685741540431041359,
            1469840572053747949720853289796099707562318378077626046833147818685776895044
        ],
        [
            2774277348282328170085742674659971495571500392161601753293416467112865068097,
            3137849475565620656681313987560185334413793189698703604034985791122356336275
        ],
        [
            672166412479844650342747861081472852496472428762577522054587528815692740558,
            1663866879616164274903483340205017481052054060286752355521506181082184021495
        ],
        [
            3180945697595716737370693680466484191429900897946060952610697010699886591271,
            370261256417300103212360232751326303498788243730491970857436044670395786744
        ],
        [
            1201682462650513594149029305106730482154241597912555054934133306913124052927,
            2702519627582077982048055809065014719130205668704469328908061241215382284753
        ],
        [
            2573098232031718801548737595348908190100964683270928802802545310591952021697,
            421880381247280215923854338509978900130125935079274502459764130391391089799
        ],
        [
            3080354619128885268149548971617703089581818473398812557354479708280835955809,
            256390985131798172675848658065159234227830929883285189158702397702435740036
        ],
        [
            3305006433068254197629607860194494003641107593674801290918966761186348868243,
            3339026583930460592461023889277320373514761589020084302062859793412730118034
        ],
        [
            1923241940978623629561560707497295652725232345651095835780507541645042579369,
            1034987404476549078390013964157937064176009291357135198452850234267991254512
        ],
        [
            1242878056067701165715334664693705019638823755244701687487484225344981621708,
            2778020811088591142544537894197696376781458923989081525073574174237563505877
        ],
        [
            103159350300766901891674139940778235823347527941771255048984655353665811131,
            2998408586900586528158477448701326671048806329090729531148457644075161991659
        ],
        [
            71218614431436475107665191107448218056096758969742620338129750710339397239,
            2301542035924343190515686028267024414404475677263930511758245534549493426119
        ],
        [
            1192223060475270158246514565467403478627193592812213292121865811070708026418,
            3208674842884877565377729626392486507374130037365033772947426862394273679084
        ],
        [
            2701994874964587709938210915198043688526355413043491003913483399075336026535,
            2886333482965974313702782452985415254520267819631653595494065556318924996302
        ],
        [
            3306009714468475346677294651301864623371911173285781201209240934162798592783,
            605466198613255313875059832114128899690381126611676641778478133738267702577
        ],
        [
            1450098270166428194278914193816868101013739489893607935042066987079292018245,
            60254834310937851613452000117427371272748499709961477924319944539270878930
        ],
        [
            3472634693037182832142729498155218303319113785483118130849719300023909673520,
            1641508292869191604146734378916767617013327049910565729753281855691648138118
        ],
        [
            1894817968472977732589643163725633598408826498334595898528746877517402007256,
            193046947184625502016096786396456839948351998258967537298275688147378157385
        ],
        [
            798518742331453195093601874576575285888369661705098199469223675278431898599,
            107377575629504498627957848614396996685294283100119805971247351789316564355
        ],
        [
            72958015465538907944252844948497831886498059248823205873862483987609118945,
            382019162223291772579736282379325284805025953290359275955015292364404489133
        ],
        [
            3314147563388677609583640640385513143694481753397403848688825124581323140921,
            3133015892701145825892878874198767217439365812782859844688129544070997319541
        ],
        [
            2444095071507078967491725470181706633826193926858202958437137361403432629390,
            3611326330343873710939978620686319096878621369582121415988028359537867630792
        ],
        [
            2107740367200683219354058003519333570583941271011338026730935614636775950367,
            953104025671531038979165726896993106119997272237926795749220750824852831326
        ],
        [
            3234656093348684616411954956071945712517868853923240328793520762092030352104,
            593797219275153872348854593022027262920747808515266478952508298984248786194
        ],
        [
            1602095369325252473599793473477096021341779224145909730627015015569257565602,
            3272207934512491788245765497830881358513949839139669547034252308088069134971
        ],
        [
            3149982146511124605253586861983261220008132001764223357617600582721741955729,
            2095033709871635786785037791315376486221829475125386227641672208905379085173
        ],
        [
            3001928273494873166012582714776651165587585607934603548408913923445707516447,
            1090266449665582127890982346068170500195143341692394417827957481874850148101
        ],
        [
            1200188694803418163698740652082064619102559508865389996854547617715365179733,
            2701249247866363010207334776256734312390753341409567681725083482804664533572
        ],
        [
            2181535855195652401374211290838795366238299923929423873085735410894622521047,
            2376412857416063533601832417302250911062085318826783757605801470091451365057
        ],
        [
            482216227882593950837484293882738923170227555670484160841935409522897080275,
            3568625956076637648484022304136932386854238480511347282187445648692365982275
        ],
        [
            2597799669063340267995599892195854202917996255210920411104497198234262573206,
            3599688873496047961188179975715306136394737017927100659789000949688648352738
        ],
        [
            1074803073878259665128704812644508804681887514658526880458531694790041080733,
            2797007314237358398853761880558407828488654212157591536243300688627270327611
        ],
        [
            468516314257643341712703808920275922572701541039900608201362821198817231181,
            1374527914917866113032496762177078616084751647116110264806150108724834406388
        ],
        [
            1208295021405021769918747031548141820393186404250802478605705170489054454157,
            1808650369660257850053512198148641736021245568921649705336796845945032764079
        ],
        [
            1565766387634045687737221757815822397332528241094852872444435795933964809539,
            3012257951756551767601579252037773433674622118381097513581891561867035592007
        ],
        [
            296854483963576847362550837105567519963678928320906132062353506063381160038,
            2997621846549637009998526882695309289938245125374301351844169021609166074993
        ],
        [
            967192065183772403576792198824105189328662921952353748318585728895552782317,
            343259257621685032456419166732348373845783852374756662051672936363788935338
        ],
        [
            456199991075423266290193634515181612721738873753897142916892886319728411618,
            3009804764464949268795409945347301690744692042792259709767667423717478448229
        ],
        [
            242210936510534966601707881924518098930470912600217515366037129037143259602,
            2698396953115175496998177800235267214917400761768300598355994305287141321271
        ],
        [
            943070145114606420402378547694273832277173459266557776382587828687889744387,
            463274201648439487604179878678549669204059390508994779482933722127905403494
        ],
        [
            958740504301613688526614902955971923282735882762427544770668882582144756278,
            1648715733425449195104866742590789175535499260400395501324113794510596751843
        ],
        [
            2738467504442851843676882768027062309179245908086784030957627999641833602734,
            403058158250173068725971433188527745485878446592356816888847490041658726521
        ],
        [
            851584175891221844656684173543344216725376446573878021753176795750916050165,
            2989949954698892115645230865442980084822288702406021287339635187958555345139
        ],
        [
            2648599427528401936572004779373684054684563511138695864967500218937169746782,
            545540526832939914359571382575431287745621956136188859527645452849687661804
        ],
        [
            2781909713387830233242081629088160756893816968845366829353355409163126437112,
            3474066345655056798683792894555452083305620276965763551620554269294421970656
        ],
        [
            62007937137219837991330947293062511223089197148302827535260096716770644685,
            3537197938414984401398955238628360208832764753222288521326061893140886724271
        ],
        [
            2379962749567351885752724891227938183011949129833673362440656643086021394946,
            776496453633298175483985398648758586525933812536653089401905292063708816422
        ],
        [
            553697491755753712548822408932664734674730150084063981046477343718694621804,
            2797798649021537247229237999331435556632872779265479409612091247299955463913
        ],
        [
            2026114267613810970244390071397350467776533880677809710454617259260017487512,
            3330593270696197494966018967263043594632970418364498628573044882141635806155
        ],
        [
            1254733481274108825174693797237617285863727098996450904398879255272288617861,
            2644890941682394074696857415419096381561354281743803087373802494123523779468
        ]
    ]

N_ELEMENT_BITS_ECDSA = math.floor(math.log(FIELD_PRIME, 2))
assert N_ELEMENT_BITS_ECDSA == 251

N_ELEMENT_BITS_HASH = FIELD_PRIME.bit_length()
assert N_ELEMENT_BITS_HASH == 252

# Elliptic curve parameters.
assert 2**N_ELEMENT_BITS_ECDSA < EC_ORDER < FIELD_PRIME

SHIFT_POINT = CONSTANT_POINTS[0]
MINUS_SHIFT_POINT = (SHIFT_POINT[0], FIELD_PRIME - SHIFT_POINT[1])
EC_GEN = CONSTANT_POINTS[1]

assert SHIFT_POINT == [
    0x49EE3EBA8C1600700EE1B87EB599F16716B0B1022947733551FDE4050CA6804,
    0x3CA0CFE4B3BC6DDF346D49D06EA0ED34E621062C0E056C1D0405D266E10268A,
]
assert EC_GEN == [
    0x1EF15C18599971B7BECED415A40F0C7DEACFD9B0D1819E03D723D8BC943CFCA,
    0x5668060AA49730B7BE4801DF46EC62DE53ECD11ABE43A32873000C36E8DC1F,
]


#########
# ECDSA #
#########

# A type for the digital signature.
ECSignature = Tuple[int, int]


class InvalidPublicKeyError(Exception):
    def __init__(self):
        super().__init__("Given x coordinate does not represent any point on the elliptic curve.")


def get_y_coordinate(stark_key_x_coordinate: int) -> int:
    """
    Given the x coordinate of a stark_key, returns a possible y coordinate such that together the
    point (x,y) is on the curve.
    Note that the real y coordinate is either y or -y.
    If x is invalid stark_key it throws an error.
    """

    x = stark_key_x_coordinate
    y_squared = (x * x * x + ALPHA * x + BETA) % FIELD_PRIME
    if not is_quad_residue(y_squared, FIELD_PRIME):
        raise InvalidPublicKeyError()
    return sqrt_mod(y_squared, FIELD_PRIME, all_roots=True)


def get_random_private_key() -> int:
    # Returns a private key in the range [1, EC_ORDER).
    return secrets.randbelow(EC_ORDER - 1) + 1


def private_key_to_ec_point_on_stark_curve(priv_key: int) -> ECPoint:
    assert 0 < priv_key < EC_ORDER
    return ec_mult(priv_key, EC_GEN, ALPHA, FIELD_PRIME)


def private_to_stark_key(priv_key: int) -> int:
    return private_key_to_ec_point_on_stark_curve(priv_key)[0]


def inv_mod_curve_size(x: int) -> int:
    return div_mod(1, x, EC_ORDER)


def generate_k_rfc6979(msg_hash: int, priv_key: int, seed: Optional[int] = None) -> int:
    # Pad the message hash, for consistency with the elliptic.js library.
    if 1 <= msg_hash.bit_length() % 8 <= 4 and msg_hash.bit_length() >= 248:
        # Only if we are one-nibble short:
        msg_hash *= 16

    if seed is None:
        extra_entropy = b""
    else:
        extra_entropy = seed.to_bytes(math.ceil(seed.bit_length() / 8), "big")

    return generate_k(
        EC_ORDER,
        priv_key,
        hashlib.sha256,
        msg_hash.to_bytes(math.ceil(msg_hash.bit_length() / 8), "big"),
        extra_entropy=extra_entropy,
    )


def sign(msg_hash: int, priv_key: int, seed: Optional[int] = None) -> ECSignature:
    # Note: msg_hash must be smaller than 2**N_ELEMENT_BITS_ECDSA.
    # Message whose hash is >= 2**N_ELEMENT_BITS_ECDSA cannot be signed.
    # This happens with a very small probability.
    assert 0 <= msg_hash < 2**N_ELEMENT_BITS_ECDSA, "Message not signable."

    # Choose a valid k. In our version of ECDSA not every k value is valid,
    # and there is a negligible probability a drawn k cannot be used for signing.
    # This is why we have this loop.
    while True:
        k = generate_k_rfc6979(msg_hash, priv_key, seed)
        # Update seed for next iteration in case the value of k is bad.
        if seed is None:
            seed = 1
        else:
            seed += 1

        # Cannot fail because 0 < k < EC_ORDER and EC_ORDER is prime.
        x = ec_mult(k, EC_GEN, ALPHA, FIELD_PRIME)[0]

        # DIFF: in classic ECDSA, we take int(x) % n.
        r = int(x)
        if not (1 <= r < 2**N_ELEMENT_BITS_ECDSA):
            # Bad value. This fails with negligible probability.
            continue

        if (msg_hash + r * priv_key) % EC_ORDER == 0:
            # Bad value. This fails with negligible probability.
            continue

        w = div_mod(k, msg_hash + r * priv_key, EC_ORDER)
        if not (1 <= w < 2**N_ELEMENT_BITS_ECDSA):
            # Bad value. This fails with negligible probability.
            continue

        s = inv_mod_curve_size(w)
        return r, s


def mimic_ec_mult_air(m: int, point: ECPoint, shift_point: ECPoint) -> ECPoint:
    """
    Computes m * point + shift_point using the same steps like the AIR and throws an exception if
    and only if the AIR errors.
    """
    assert 0 < m < 2**N_ELEMENT_BITS_ECDSA
    partial_sum = shift_point
    for _ in range(N_ELEMENT_BITS_ECDSA):
        assert partial_sum[0] != point[0]
        if m & 1:
            partial_sum = ec_add(partial_sum, point, FIELD_PRIME)
        point = ec_double(point, ALPHA, FIELD_PRIME)
        m >>= 1
    assert m == 0
    return partial_sum


def is_point_on_curve(x: int, y: int) -> bool:
    return pow(y, 2, FIELD_PRIME) == (pow(x, 3, FIELD_PRIME) + ALPHA * x + BETA) % FIELD_PRIME


def is_valid_stark_private_key(private_key: int) -> bool:
    """
    Returns whether the given input is a valid STARK private key.
    """
    return 0 < private_key < EC_ORDER


# def is_valid_stark_key(stark_key: int) -> bool:
#     """
#     Returns whether the given input is a valid STARK key.
#     """
#     # Only the x coordinate of the point is given, get the y coordinate and make sure that the
#     # point is on the curve.
#     try:
#         get_y_coordinate(stark_key_x_coordinate=stark_key)
#     except InvalidPublicKeyError:
#         return False
#     return True


# def verify(msg_hash: int, r: int, s: int, public_key: Union[int, ECPoint]) -> bool:
#     # Compute w = s^-1 (mod EC_ORDER).
#     assert 1 <= s < EC_ORDER, "s = %s" % s
#     w = inv_mod_curve_size(s)

#     # Preassumptions:
#     # DIFF: in classic ECDSA, we assert 1 <= r, w <= EC_ORDER-1.
#     # Since r, w < 2**N_ELEMENT_BITS_ECDSA < EC_ORDER, we only need to verify r, w != 0.
#     assert 1 <= r < 2**N_ELEMENT_BITS_ECDSA, "r = %s" % r
#     assert 1 <= w < 2**N_ELEMENT_BITS_ECDSA, "w = %s" % w
#     assert 0 <= msg_hash < 2**N_ELEMENT_BITS_ECDSA, "msg_hash = %s" % msg_hash

#     if isinstance(public_key, int):
#         # Only the x coordinate of the point is given, check the two possibilities for the y
#         # coordinate.
#         try:
#             y = get_y_coordinate(public_key)
#         except InvalidPublicKeyError:
#             return False
#         return verify(msg_hash, r, s, (public_key, y)) or verify(
#             msg_hash, r, s, (public_key, (-y) % FIELD_PRIME)
#         )

#     # The public key is provided as a point.
#     assert is_point_on_curve(x=public_key[0], y=public_key[1])

#     # Signature validation.
#     # DIFF: original formula is:
#     # x = (w*msg_hash)*EC_GEN + (w*r)*public_key
#     # While what we implement is:
#     # x = w*(msg_hash*EC_GEN + r*public_key).
#     # While both mathematically equivalent, one might error while the other doesn't,
#     # given the current implementation.
#     # This formula ensures that if the verification errors in our AIR, it errors here as well.
#     try:
#         zG = mimic_ec_mult_air(msg_hash, EC_GEN, MINUS_SHIFT_POINT)
#         rQ = mimic_ec_mult_air(r, public_key, SHIFT_POINT)
#         wB = mimic_ec_mult_air(w, ec_add(zG, rQ, FIELD_PRIME), SHIFT_POINT)
#         x = ec_add(wB, MINUS_SHIFT_POINT, FIELD_PRIME)[0]
#     except AssertionError:
#         return False

#     # DIFF: Here we drop the mod n from classic ECDSA.
#     return r == x


def grind_key(key_seed: int, key_value_limit: int) -> int:  # type: ignore[return]
    """
    Given a cryptographically-secure seed and a limit, deterministically generates a pseudorandom
    key in the range [0, limit).
    This is a reference implementation, and cryptographic security is not guaranteed (for example,
    it may be vulnerable to side-channel attacks); this function is not recommended for use with key
    generation on mainnet.
    """
    # Simply taking a uniform value in [0, 2**256) and returning the result modulo key_value_limit
    # is not necessarily uniform on [0, key_value_limit). We define max_allowed_value to be a
    # multiple of the limit, so that a uniform sample of [0, max_allowed_value) mod key_value_limit
    # is uniform on [0, key_value_limit).
    max_allowed_value = 2**256 - (2**256 % key_value_limit)

    def to_bytes_no_pad(x: int) -> bytes:
        # To conform with the JS implementation, convert integer to bytes using minimal amount of
        # bytes possible. We would like 0.to_bytes() to be b'\x00', so a minimal length of 1 is
        # enforced.
        return x.to_bytes(length=max(1, div_ceil(x.bit_length(), 8)), byteorder="big", signed=False)

    # Increment the index (salt) until the hash value falls in the range [0, max_allowed_value).
    for index in itertools.count():
        hash_input = to_bytes_no_pad(key_seed) + to_bytes_no_pad(index)
        key = int(hashlib.sha256(hash_input).hexdigest(), 16)
        if key < max_allowed_value:
            return key % key_value_limit


#################
# Pedersen hash #
#################


def pedersen_hash(*elements: int) -> int:
    return pedersen_hash_as_point(*elements)[0]


def pedersen_hash_as_point(*elements: int) -> ECPoint:
    """
    Similar to pedersen_hash but also returns the y coordinate of the resulting EC point.
    This function is used for testing.
    """
    point = SHIFT_POINT
    for i, x in enumerate(elements):
        assert 0 <= x < FIELD_PRIME
        point_list = CONSTANT_POINTS[
            2 + i * N_ELEMENT_BITS_HASH : 2 + (i + 1) * N_ELEMENT_BITS_HASH
        ]
        assert len(point_list) == N_ELEMENT_BITS_HASH
        for pt in point_list:
            assert point[0] != pt[0], "Unhashable input."
            if x & 1:
                point = ec_add(point, pt, FIELD_PRIME)
            x >>= 1
        assert x == 0
    return point
